/*
 * @Author: qianmingtian
 * @Date: 2020-07-09 17:58:27
 * @LastEditors: qianmingtian
 * @LastEditTime: 2020-07-09 21:00:50
 * @FilePath: \qianmingtian.github.io\code\java\SortAlogrithm\HalfSelect.java
 */
package SortAlogrithm;

public class HalfSelect {
    public static void main(String[] args) {
        int[] arr = { 123, 34, 5, 6, 21, 6543, 231, 6453, 213 };
        arr = PaoPaoSort.sortByPaoPao(arr);
        PaoPaoSort.showArr(arr); // 5 6 21 34 123 213 231 6453 6543

        int result = binarySearch(arr, 6543);
        System.out.println(result);

        int result02 = binarySearchBy(arr, 0, arr.length - 1, 6);
        System.out.println(result02);

    }

    /**
     * 从数组中查找目标元素的下标
     * 
     * @param arr    被查找数组
     * @param target 目标元素
     * @return -1 不存在，其他返回下标
     */

    public static int binarySearch(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = (start + end) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return -1;

    }

    public static int binarySearchBy(int[] arr, int begin, int end, int target) {
        if (begin <= end) {
            int mid = (begin + end) / 2;

            if (target == arr[mid]) {
                return mid;
            } else if (arr[mid] < target) {
                return binarySearchBy(arr, mid + 1, end, target);
            } else if (arr[mid] > target) {
                return binarySearchBy(arr, begin, mid - 1, target);
            }

        }
        return -1;
        
    }
}/*
  * @Author: qianmingtian
  * 
  * @Date: 2020-07-09 17:58:27
  * 
  * @LastEditors: qianmingtian
  * 
  * @LastEditTime: 2020-07-09 17:58:27
  * 
  * @FilePath: \qianmingtian.github.io\code\java\SortAlogrithm\HalfSelect.java
  */
